package gold.contest;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC6113 {
    public long startExecuteTime = System.currentTimeMillis();


    class SmallestInfiniteSet {

        TreeSet<Integer> poped = new TreeSet<>();
        TreeSet<Integer> backed = new TreeSet<>();
        int normalIdx = 1;

        public SmallestInfiniteSet() {

        }

        public int popSmallest() {
            if (!backed.isEmpty() && backed.first() < normalIdx) {
                Integer first = backed.first();
                backed.remove(first);
                poped.add(first);
                System.out.println("popSmallest return backedSet value : " + first);
                return first;
            }

            poped.add(normalIdx);
            backed.remove(normalIdx);
            System.out.println("popSmallest return normalIdx value : " + normalIdx);
            return normalIdx++;
        }

        public void addBack(int num) {
            backed.add(num);
            poped.remove(num);
        }
    }


    public void run() {
        SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
        smallestInfiniteSet.addBack(2);    // 2 已经在集合中，所以不做任何变更。
        smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 是最小的整数，并将其从集合中移除。
        smallestInfiniteSet.popSmallest(); // 返回 2 ，并将其从集合中移除。
        smallestInfiniteSet.popSmallest(); // 返回 3 ，并将其从集合中移除。
        smallestInfiniteSet.addBack(1);    // 将 1 添加到该集合中。
        smallestInfiniteSet.popSmallest(); // 返回 1 ，因为 1 在上一步中被添加到集合中，
        // 且 1 是最小的整数，并将其从集合中移除。
        smallestInfiniteSet.popSmallest(); // 返回 4 ，并将其从集合中移除。
        smallestInfiniteSet.popSmallest(); // 返回 5 ，并将其从集合中移除。
    }

    public static void main(String[] args) throws Exception {
        LC6113 an = new LC6113();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
